package com.LeeCode;

import java.util.HashMap;

/**
 * 在线选举
 */

public class Code911 {
    public static void main(String[] args) {
        int[] persons = {0, 1, 1, 0, 0, 1, 0};
        int[] times = {0, 5, 10, 15, 20, 25, 30};
        TopVotedCandidate topVotedCandidate = new Code911().new TopVotedCandidate(persons, times);
        System.out.println(topVotedCandidate.q(3));
        System.out.println(topVotedCandidate.q(12));
        System.out.println(topVotedCandidate.q(25));
        System.out.println(topVotedCandidate.q(15));
        System.out.println(topVotedCandidate.q(24));
        System.out.println(topVotedCandidate.q(8));
    }

    class TopVotedCandidate {
        private int[] winner;
        private int[] times;

        public TopVotedCandidate(int[] persons, int[] times) {
            this.times = times;
            winner = new int[times.length];
            HashMap<Integer, Integer> map = new HashMap<>();

            int leader = -1, maxVote = 0;

            for (int i = 0; i < times.length; i++) {
                int p = persons[i];
                map.merge(p, 1, Integer::sum);
                int vote = map.get(p);
                if (vote >= maxVote) {
                    maxVote = vote;
                    leader = p;
                }
                winner[i] = leader;
            }

        }

        public int q(int t) {
            int index = lowerBound(t + 1) - 1;
            return winner[index];
        }

        private int lowerBound(int target) {
            int left = -1, right = times.length;
            while (left + 1 < right) {
                int mid = left + (right - left) / 2;
                if (times[mid] >= target) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            return right;
        }
    }
}
